package chapter02_linkedList;

/**
 * 描述：
 *      将链表分为左边小、中间相等、右边大的形式
 *      进阶：维持原来的相对顺序，并且空间复杂度做到O(1)
 * @author hl
 * @date 2021/1/28 11:20
 */
public class ListPartition {
    public static void main(String[] args) {
        Node head = new Node(5);
        head.next = new Node(3);
        head.next.next = new Node(4);
        head.next.next.next = new Node(-1);
        head.next.next.next.next = new Node(7);
        Node node = new ListPartition().listPartition2(head, 3);
        System.out.println(node);
    }


    /**
     * 将链表转换为数组，使用数组进行partition过程
     * @param head
     * @param pivot
     * @return
     */
    public Node listPartition1(Node head, int pivot){
        if (head == null) {
            return null;
        }
        Node cur = head;
        int index = 0;
        while(cur != null){
            index++;
            cur = cur.next;
        }
        Node[] arr = new Node[index];
        cur = head;
        index = 0;
        while(cur != null){
            arr[index++] = cur;
            cur = cur.next;
        }
        partition(arr, 0, arr.length - 1, pivot);
        //将数组串起来
        for (int i = 1; i < arr.length; i++) {
            arr[i - 1].next = arr[i];
        }
        arr[arr.length - 1].next = null;
        return arr[0];
    }

    private void partition(Node[] arr, int l, int r, int pivot) {
        int less = l - 1;
        int more = r + 1;
        while(l < more){
            if (arr[l].val < pivot) {
                swap(arr, l++, ++less);
            }else if (arr[l].val > pivot) {
                swap(arr, l, --more);
            }else{
                l++;
            }
        }
    }

    public void swap(Node[] arr, int i, int j){
        Node temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 分成small、equals、big三个链表
     * @param head
     * @param pivot
     * @return
     */
    public Node listPartition2(Node head, int pivot){
        Node smallH = null;
        Node smallT = null;
        Node equalsH = null;
        Node equalsT = null;
        Node bigH = null;
        Node bigT = null;
        Node cur = head;
        Node next = null;
        while(cur != null){
            next = cur.next;
            cur.next = null;
            if (cur.val < pivot) {
                if (smallH == null) {
                    smallH = cur;
                    smallT = cur;
                }else{
                    smallT.next = cur;
                    smallT = cur;
                }
            }else if (cur.val == pivot) {
                if(equalsH == null){
                    equalsH = cur;
                    equalsT = cur;
                }else{
                    equalsT.next = cur;
                    equalsT = cur;
                }
            }else{
                if(bigH == null){
                    bigH = cur;
                    bigT = cur;
                }else{
                    bigT.next = cur;
                    bigT = cur;
                }
            }
            cur = next;
        }

        if (smallT != null) {
            smallT.next = equalsH;
            smallT = equalsT == null ? smallT : equalsT;
        }
        if (equalsT != null) {
            equalsT.next = bigH;
            equalsT = bigT == null ? equalsT : bigT;
        }
        return smallH != null ? smallH : equalsH != null ? equalsH : bigH;
    }

}
